/**
 * 72. 编辑距离
 * https://leetcode-cn.com/problems/edit-distance/
 */

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
function minDistance(word1, word2) {
  const dp = new Array(word1.length + 1);
  for (let i = 0; i <= word1.length; i += 1) {
    dp[i] = new Array(word2.length + 1).fill(0);
  }
  for (let i = 1; i <= word1.length; i += 1) {
    dp[i][0] = i;
  }
  for (let j = 1; j <= word2.length; j += 1) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= word1.length; i += 1) {
    for (let j = 1; j <= word2.length; j += 1) {
      dp[i][j] = Math.min(
        dp[i - 1][j] + 1,
        dp[i][j - 1] + 1,
        dp[i - 1][j - 1] + (word1.charCodeAt(i - 1) === word2.charCodeAt(j - 1) ? 0 : 1),
      );
    }
  }
  return dp[word1.length][word2.length];
}

console.log(minDistance('horse', 'ros') === 3);
console.log(minDistance('intention', 'execution') === 5);
